#include <stdio.h>
#include <stdlib.h>
/*
如何确定哪些是要调整的节点

左旋

右旋

如何计算平衡因子？
拿左孩子的高度减去右孩子的高度，平衡的结果为-1,0,1 ， 不平衡标记为需要调整
在 Insert 函数递归回退时，将自下而上的计算每一个节点的平衡因子。

如何计算左右孩子的高度？
在 insert 函数中使一个递归的过程，每次新增加一个节点，都将调用 create 函数，这个函数将新节点的高度设置为 1。在递归回退的时候，
自下而上的更新路过的每一个节点的高度。
*/
// AVL树节点定义
typedef struct AVLTreeNode {
    int data;                       // 节点值
    struct AVLTreeNode* left;       // 左子树
    struct AVLTreeNode* right;      // 右子树
    int height;                     // 节点高度
} AVLTreeNode;

// 获取节点高度
int height(AVLTreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 创建一个新节点
AVLTreeNode* createNode(int data) {
    AVLTreeNode* node = (AVLTreeNode*)malloc(sizeof(AVLTreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;  // 新节点的初始高度为1
    return node;
}

// 右旋转
AVLTreeNode* rightRotate(AVLTreeNode* y) {
    AVLTreeNode* x = y->left;//x 为当前节点的左孩子，即新插入的节点
    AVLTreeNode* T2 = x->right;//t2 为当前节点左孩子的右孩子，NULL

    // 执行旋转
    x->right = y;//
    y->left = T2;

    // 更新高度
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));

    return x;  // 返回新的根节点
}

// 左旋转
AVLTreeNode* leftRotate(AVLTreeNode* x) {
    AVLTreeNode* y = x->right; // y 为新插入的节点，它导致了树的失衡
    AVLTreeNode* T2 = y->left; //  t2 为新插入节点的左孩子，null

    // 执行旋转
    y->left = x;  //将父节点设置为新插入节点的左孩子
    x->right = T2; //

    // 更新高度
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));

    return y;  // 返回新的根节点
}

// 获取节点的平衡因子
int getBalance(AVLTreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);// -1,0,1 为平衡状态
}

// 插入节点
AVLTreeNode* insert(AVLTreeNode* node, int data) {
    // 1. 普通的二叉查找树插入
    if (node == NULL) {
        return createNode(data); //height 设置为 1
    }

    if (data < node->data) {
        node->left = insert(node->left, data);
    } else if (data > node->data) {
        node->right = insert(node->right, data);
    } else {
        // 相同的数据不允许插入
        return node;
    }

    // 2. 更新节点高度，这里在递归的过程中，为每一个新节点都设置其作为子树的高度。
    node->height = 1 + (height(node->left) > height(node->right) ? height(node->left) : height(node->right));

    // 3. 检查节点是否失衡，这里在递归的过程中，将检查所有相关节点的平衡因子
    int balance = getBalance(node);

    // 左左情况 LL 型
    if (balance > 1 && data < node->left->data) {//插入到左子树的左子树上
        return rightRotate(node);
    }

    // 右右情况 RR 型
    if (balance < -1 && data > node->right->data) {//插入到右子树的右子树上
        return leftRotate(node);
    }

    // 左右情况 LR 型
    if (balance > 1 && data > node->left->data) {//balance = 2, data > node->left->data, node 为根节点
        node->left = leftRotate(node->left);//传入根节点的左孩子，即原本要接入的位置的父节点
        return rightRotate(node);
    }

    // 右左情况 RL 型
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;  // 返回（可能更新过的）根节点
}

// 中序遍历
void inorderTraversal(AVLTreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// 获取最小值节点（用于删除时找到中序后继）
AVLTreeNode* findMin(AVLTreeNode* node) {
    AVLTreeNode* current = node;
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}

// 删除节点
AVLTreeNode* deleteNode(AVLTreeNode* root, int data) {
    if (root == NULL) {
        return root;
    }

    // 1. 执行标准的二叉查找树删除
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        // 找到要删除的节点
        if (root->left == NULL || root->right == NULL) {
            AVLTreeNode* temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                // 没有子节点
                temp = root;
                root = NULL;
            } else {
                // 只有一个子节点
                *root = *temp;
            }
            free(temp);
        } else {
            // 有两个子节点，找到中序后继
            AVLTreeNode* temp = findMin(root->right);//找到右子树中的最小节点
            root->data = temp->data;//用最小节点覆盖要删除的节点
            root->right = deleteNode(root->right, temp->data);//删除最小节点
        }
    }

    if (root == NULL) {
        return root;
    }

    // 2. 更新节点高度，递归过程，回退时更新所有节点的高度
    root->height = 1 + (height(root->left) > height(root->right) ? height(root->left) : height(root->right));

    // 3. 检查节点是否失衡，递归过程，回退时更新所有节点的平衡因子
    int balance = getBalance(root);

    // 左左情况，递归过程，回退时调整所有 LL 型
    if (balance > 1 && getBalance(root->left) >= 0) {//失衡
        return rightRotate(root);
    }

    // 左右情况，递归过程，回退时调整所有 RL 型
    if (balance > 1 && getBalance(root->left) < 0) {//失衡
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // 右右情况，递归过程，回退时调整所有 RR 型
    if (balance < -1 && getBalance(root->right) <= 0) { //失衡
        return leftRotate(root);
    }

    // 右左情况
    if (balance < -1 && getBalance(root->right) > 0) { //失衡
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

// 主函数
int main() {
    AVLTreeNode* root = NULL;

    // 插入节点
    root = insert(root, 40);

    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 50);
    root = insert(root, 25);

    // 输出中序遍历
    printf("Inorder traversal of the AVL tree is: ");
    inorderTraversal(root);
    printf("\n");

    // 删除节点
    root = deleteNode(root, 50);
    printf("Inorder traversal after deleting 50: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}
